import java.util.List;

/**
 * 二分搜索法demo
 * 前提：被搜索的数组必须为有序
 * 思路：每次获取数组中的中间元素值middle和key进行比较，
 * 如果middle==key,则返回key的索引；
 * 如果middle>key,则将数组的前半部分排除，用相同的方法搜索数组的后半部分；
 * 如果middle<key,则将数组的后半部分排除，用相同的方法搜索数组的前半部分；
 *
 * @author HuRui
 * create on 2018/12/23 8:45 AM
 */
public class BinarySearch {
    /**
     * 循环的方式实现二分查找
     *
     * @param ts  待搜索的有序数组
     * @param key 需要查询的值
     * @return key值在数组中的索引值，如果为-1则表示不存在
     */
    public static int binarySearch(Comparable[] ts, Comparable key) {
        if (ts == null || ts.length == 0 || key == null) {
            return -1;
        }
        int left = 0, right = ts.length - 1;
        while (left < right) {
//            int middle = (left + right) / 2;
            //防止int溢出
            int middle = left + (right - left) >> 1;
            Comparable t = ts[middle];
            if (key.compareTo(t) == 0) {
                return middle;
            } else if (key.compareTo(t) < 0) {
                right = middle - 1;
            } else {
                left = middle - 1;
            }
        }
        return -1;
    }

    /**
     * 递归的方式实现二分搜索法
     *
     * @param left        左边界
     * @param right       右边界
     * @param comparables 待查找数组
     * @param comparable  关键值
     * @return 关键值在数组中的索引
     */
    public static int recursion(int left, int right,
                                Comparable[] comparables, Comparable comparable) {
        if (left > right) {
            return -1;
        }
        int middle = left + (right - left) >> 1;
        if (comparable.compareTo(comparables[middle]) == 0) {
            return middle;
        } else if (comparable.compareTo(comparables[middle]) > 0) {
            return recursion(middle + 1, right, comparables, comparable);
        } else {
            return recursion(left, middle - 1, comparables, comparable);
        }
    }
}
